export const binarySearchR = (data, target) => {
    return search(data, 0, data.length - 1, target)
}

const search = (data, l, r, target) => {
    if (l > r) {
        return -1
    }

    const mid = Math.floor(l + (r - l) / 2)
    // const mid = Math.floor((l + r) / 2)

    if (data[mid] === target) {
        return mid
    }

    if (data[mid] < target) {
        return search(data, mid + 1, r, target)

    } else {
        return search(data, l, mid - 1, target)

    }

}

export const binarySearch = (data, target) => {
    let l = 0
    let r = data.length - 1

    while (l <= r) {
        const mid = Math.floor((l + r) / 2)

        if (data[mid] === target) {
            return mid
        }

        if (data[mid] < target) {
            l = mid + 1
        } else {
            r = mid - 1
        }

    }

    return -1
}

// 问题定义一定有解，大于 target 的最小值
export const upper = (data, target) => {
    let l = 0
    let r = data.length

    while (l < r) {
        const mid = Math.floor((l + r) / 2)
        if (data[mid] <= target) {
            l = mid + 1

        } else {
            r = mid
        }
    }

    return l
}

// 如果数组存在元素，然后最大索引，不存在则返回 upper
export const ceil = (data, target) => {
    const u = upper(data, target)

    if (u - 1 >= 0 && data[u - 1] === target) {
        return u - 1
    }

    return u
}

// 小于 target 的最大值
export const lower = (data, target) => {
    let l = -1
    let r = data.length - 1

    while (l < r) {
        const mid = Math.floor((l + r + 1) / 2)
        if (data[mid] < target) {
            l = mid

        } else {
            r = mid - 1
        }
    }

    return l
}